package leetcode.algorithm.linkedlist.simple.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import javafx.util.Pair;
import leetcode.algorithm.TreeHelper;
import leetcode.algorithm.TreeNode;

/**
 * @author jiangwz
 * @create 2019/11/11.
 */
public class Temp {

    //q897
    public static void main(String[] args){
        System.out.println(Integer.valueOf("100", 2));
        Queue<String> queue = new LinkedList<>();
        ((LinkedList<String>) queue).pollLast();
        Temp t = new Temp();
        Pair<String,String> p = new Pair<>("1","2");
        Integer[] arr = new Integer[]{5,3,6,2,4,null,8,1,null,null,null,null,null,7,9};
        TreeNode treeNode = TreeHelper.array2Tree(arr);
//        TreeNode treeNode1 = t.increasingBST(treeNode);
//        System.out.println(treeNode1);
        System.out.println(t.increasingBSTNoRecursion(treeNode));

        System.out.println(t.pathSum(TreeHelper.array2Tree(new Integer[]{10,5,-3,3,2,null,11,3,-2,null,1}), 8));
        System.out.println(t.isCousins(TreeHelper.array2Tree(new Integer[]{1,2,5,3,null,null,6,4}), 3, 6));

    }

    public int pathSum(TreeNode root, int sum) {
        if(root==null)
            return 0;
        //key是前缀和, value是大小为key的前缀和出现的次数
        HashMap<Integer,Integer> prefixSum = new HashMap<>();
        //非常细节的初始化, 得结合案例体会,比如案例1→1,target=2
        prefixSum.put(0,1);
        return core(prefixSum, sum, root, 0);
    }
    public int core(HashMap<Integer,Integer> prefixSum, int target, TreeNode root, int currSum){
        //base case
        if(root==null)
            return 0;
        currSum = currSum + root.val;
        //先看看root到当前节点这条路上是否存在节点value加和为target的路径
        int res = prefixSum.getOrDefault(currSum-target, 0);
        //更新前缀和的哈希表
        prefixSum.put(currSum, prefixSum.getOrDefault(currSum,0) + 1);
        //新条件新递归; 按照该方式处理左子树和右子树
        int leftRes = core(prefixSum, target, root.left, currSum);
        int rightRes = core(prefixSum, target, root.right, currSum);
        //恢复现场, 从而保证prefixSum中的记录都是投一个branch上的
        prefixSum.put(currSum, prefixSum.get(currSum)-1);
        return res + leftRes + rightRes;
    }



    // q897
    public TreeNode increasingBST(TreeNode root) {
        return inOrder(root, null);

    }

    public TreeNode inOrder(TreeNode root,TreeNode newNode){
        if(root == null){
            return null;
        }
        if(root.left != null){
            newNode =  inOrder(root.left, newNode);
        }
        if(newNode == null){
            newNode = new TreeNode(root.val);
        }else {
            add(root, newNode);
        }
        if(root.right != null){
            newNode = inOrder(root.right, newNode);
        }
        return newNode;
    }

    public void add(TreeNode root,TreeNode newNode){
        TreeNode temp = newNode;
        while(temp.right != null){
            temp = temp.right;
        }
        temp.right = new TreeNode(root.val);
    }

    public TreeNode increasingBSTNoRecursion(TreeNode root) {
        TreeNode ans = new TreeNode(0);
        TreeNode temp = ans;
        Stack<TreeNode> stack = new Stack();
        TreeNode cur = root;
        while(cur!=null || !stack.isEmpty()){
            while(cur != null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            temp.right = cur;
            temp = temp.right;
            temp.left = null;//把他原本的左节点置空
            cur = cur.right;

        }
        return ans.right;

    }


    /**
     * q993
     */

    int xLevel = 0;
    int yLevel = 0;
    TreeNode xNode = null;
    TreeNode yNode = null;
    TreeNode xP = null;
    TreeNode yP = null;

    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<Pair<TreeNode,Integer>> queue = new LinkedList();
        if(root == null){
            return false;
        }
        queue.add(new Pair(root,0));
        TreeNode parent = null;
        while(!queue.isEmpty()){
            Pair<TreeNode,Integer> p =  queue.poll();
            TreeNode n =  p.getKey();
            Integer level = p.getValue();
            if(n.val==x){
                xLevel = level;
                xNode = n;
            }
            if(n.val == y){
                yLevel = level;
                yNode = n;
            }

            if(n.left != null){
                if(n.left.val == x){
                    xP = n;
                    xNode = n.left;
                    xLevel = level+1;
                }
                else if(n.left.val == y){
                    yP = n;
                    yNode = n.left;
                    yLevel = level+1;
                }else {
                    queue.add(new Pair(n.left, level+1));
                }

            }
            if(n.right!= null){
                if(n.right.val == y){
                    yP = n;
                    yNode = n.right;
                    yLevel = level+1;
                }
                else if(n.right.val == x){
                    xP = n;
                    xNode = n.right;
                    xLevel = level+1;
                }
                else {
                    queue.add(new Pair(n.right, level+1));
                }
            }


        }
        if(xNode!=null && yNode!= null &&
                xLevel == yLevel &&

                yP!=null &&
                yP!=xP){
            return true;
        }
        return false;

    }

    public int height(TreeNode node){
        if(node == null){
            return 0;
        }
        return Math.max(node.left == null?0:height(node.left), node.right == null?0:height(node.right))+1;
    }
}
